11450 - Wedding shopping/11450.cpp

   1 /*
   2   Accepted
   3  */
   4 #include <iostream>
   5 #include <vector>
   6 #include <algorithm>
   7
   8 using namespace std;
   9
  10 int main(){
  11   int N;
  12   cin >> N;
  13   while (N--){
  14     int T, C;
  15     cin >> T >> C;
  16     vector< vector<int> > w;
  17     for (int i=0; i<C; ++i){
  18       int K;
  19       cin >> K;
  20       vector<int> row(K);
  21       for (int j=0; j<K; ++j){
  22         cin >> row[j];
  23       }
  24       w.push_back(row);
  25     }
  26
  27     bool dp[T+1][C];
  28     memset(dp, 0, sizeof dp);
  29
  30     for (int j=0; j<w[0].size(); ++j){
  31       dp[w[0][j]][0] = true; //Primer nivel
  32     }
  33
  34     for (int i=1; i<C; ++i){
  35       for (int t=0; t<=T; ++t){
  36         for (int j=0; j<w[i].size(); ++j){
  37           if (t - w[i][j] >= 0){
  38             if (dp[t-w[i][j]][i-1]){
  39               dp[t][i] = true;
  40             }
  41           }
  42         }
  43       }
  44     }
  45
  46     bool solved = false;
  47     for (int t=T; t>=0; --t){
  48       if (dp[t][C-1]){
  49         cout << t << endl;
  50         solved = true;
  51         break;
  52       }
  53     }
  54
  55     if (!solved){
  56       cout << "no solution" << endl;
  57     }
  58   }
  59   return 0;
  60 }